数据结构与算法 - 图的储存遍历及图的排序(Day3)

图
- 图是图形结构的简称, 是一种复杂非线性数据结构.
- 图的二元组是G=(V,E), V为非空的顶点集合, E为V上的二元关系集合

多对多的数据结构, 每个点和若干个点存在关系.
分类:
- 无向图
  - 边集E(G)中为无向边
- 有向图
  - 边集E{G}中为有向边
- 带权图
  - 边上带权的图, 也称为网(有向带权图, 无向带权图)
概念:
- 顶点的度
  - 与顶点相关联的边的数目
  - 奇点, 偶点: 由度的奇偶决定
  - 一个图中, 全部顶点的度数为所有边数的2倍
  - 有向图中所有顶点入度之和等于所有顶点的出度之和
  - 任意一个无向图一定有偶数个奇点
- 入度(有向图)
  - 射向顶点的边的数量
- 出度(有向图)
  - 顶点发出的边的数量
- 完全图
  - 若在无向图中, 则每两个顶点之间都存在一条边
  - 若在有向图中, 则每两个顶点之间都存在方向相反的两条边
  - 一个n阶的完全无向图含有n(n-1)/2条边
  - 一个n阶的完全有向图含有n(n-1)条边
- 稠密图
  - 一个图的边数接近完全图时
- 稀疏图
  - 一个图的边数远远少于完全图时
- 子图
  - 设两个图G=(V,E) 和 G’=(V’, E’). 若V’是V的子集, 且E’是E的子集, 则G’是G的子图
- 路径
  - 对于图G=(V,E), 对于顶点a, b, 若存在一些顶点序列x1=a,x2,…,xk=b, 且(xi,..,xi+1)属于E,
    
    i=1,2,…k-i, 则称顶点序列x1.x2,…,xk为顶点a到顶点b的一条路径, 而路径上边的数目(k-1)
    
    称为该路径的长度. 并称顶点集合{x1,x2,…,xk}为一个连通集
  - 简单路径: 若一条路径上的顶点除了起点和终点可以相同外, 其他顶点均不相同, 则称该路径为一条简单路径
- 回路
  - 起点和终点相同的简单路径称为回路(或环)
- 连通
  - 在一个图中若从顶点U到顶点V是连通的, 则称U和V是连通的
- 连通图
  - 若一个无向图中, 任意两个顶点之间都是连通的, 则称该无向图为连通图, 否则为非连通图.
- 连通分量
  - 一个无向图的连通分支定义为改图的最大连通子图.
- 强连通图
  - 在一个有向图中, 对于任意两个顶点U和V, 都存在一条从U到V以及从V到U的有向路径. 则称该有向图为强连通图
  - 一个有向图的连通分量为该图的最大强连通子图.
  - 强连通图只有一个强连通分量, 为它本身.

图的存储

分为静态存储和动态存储

静态
- 邻接矩阵(顺序存储)
  - 是表示顶点之间相邻关系党的矩阵
  - 设G(V,E)是具有n个顶点的图, 顶点序号依次为1,2,…,n. 则G的邻接矩阵是具有如下定义的n阶方阵
    - A[i,j]: 若Vi和Vj有边(对于有向图, 存在Vi->Vj的边), 则为1, 否则为0
  - 对于带权图G(V,E), 则G的邻接矩阵是如下的n阶方阵
    - A[i,j]: 若Vi和Vj有边(对于有向图, 存在Vi->Vj的边), 则为该边的权值, 否则为∞或负数
- 边集数组
动态
- 邻接表(链式存储)
  - 是对图中的每个顶点建立一个邻接关系的单链表,并把他们的表头指针用向量存储的一种图的表示方法
  - 对于有向图, 存在逆邻接表

#include <iostream>
using namespace std;
const int maxn = 1001, maxm = 100001;
struct Edge{
  int next, to;	//to: 终点,next: 和这条边具有相同起点的下一条边
}edge[maxm];

int head[maxn],num_edge,n,m,u,v;
//head[i]表示的是由i发出的第一条边的编号
void add_edge(int from, int to){
  edge[++num_edge].next = head[from];
  edge[num_edge].to = to;
  head[from] = num_edge;
}

图的遍历

深度优先遍历

只要前面有路可走, 就走, 否则回溯

//DFS Sample
#include <cstdio>
const int maxn=1010;
int a[maxn][maxn];	//邻接矩阵
int vis[maxn];	//是否遍历过
int n, m;

void dfs(int u){
  printf("%d ", u);
  vis[u] = 1;
  for(int i = 1;i<n;i++)
    if(a[u][i] == 1 && vis[i] = 0)
      dfs(i);
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i = 0; i<m;i++){
    int x, y;
    scanf("%d%d",&x,&y);
    a[x][y] = a[y][x] = 1;
  }
  dfs(1);
  return 0;
}

广度(宽度)优先遍历

先遍历起点, 然后遍历起点通过i步可到达的点, 直到i达到最大.

//BFS Sample
#include <cstdio>
const int maxn = 1010;
int a[maxn][maxn];
int vis[maxn];
int q[maxn];
int n, m;

void bfs(int u){
  int head = 0, tail = 1;
  q[0] = u;
  vis[u] = 1;
  while(head<tail){
    int p = q[head++];
    printf("%d ", u);
    for(int i = 1; i<=n; i++){
      if(a[p][i] == 1 && vis[i] == 0){
        q[tail++] = i;
        vis[i] = 1;
      }
    }
  }
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i = 0; i<m;i++){
    int x, y;
    scanf("%d%d",&x,&y);
    a[x][y] = a[y][x] = 1;
  }
  bfs(1);
  return 0;
}

若非连通图

int main(void){
  //...
  for(int i = 1;i<=n;i++)
  	if(vis[i] == 0)
  		dfs(i);	//bfs(i);
  //...
}

顶点活动网络(AOV网)
- 一项子工程要在其他一些子工程完成之后才能进行, 子工程之间的关系用有向图表示.
  
  这种有向图叫做顶点活动网络
- 一个AOV网必定是一个有向无环图, 不应带有回路.
- 拓扑排序算法
  - 把AOV网排成一个序列, 使得每个活动所有前驱活动都排在该活动的前面, 该过程称为拓扑排序, 该序列称为拓扑序列
  - 拓扑序列不唯一
  - 生成拓扑序列:
    1. 输出入度为0的点, 并删除该点的射出线, 将被删除线的终点入度减一
    2. 若全部的点皆输出, 则完成拓扑序列, 否则回到一
    - 算法实现
      1. 数据结构: indgr[i]:顶点i的入度; stack[]:栈
      2. 初始化: top=0
      3. 将初始状态的所有入度为0的顶点入栈
      4. I=0(计数器)
      5. while(栈非空)
        
        栈顶的顶点v出栈: top-1;输出v;i++
        
        遍历v后的每一个后继顶点u
        
        indgr[u]–; //u的入度-1
        
        if(u的入度为0)
        
        顶点u入栈
      6. 算法结束
      - 算法复杂度: O(V+E)

在辣鸡的领域摸爬滚打

[OI 基础] 数据结构与算法 - 图的储存遍历及图的排序

数据结构与算法 - 图的储存遍历及图的排序(Day3)

图

顶点活动网络(AOV网)